class Dictionary {
	public:
		int size() {
			return list.size();
		}
		int readDictionaryFile(string filename) {
			// opens filename and reads all expressions - one expression per line
			// returns true if successful, false if not
			ifstream dictFile;
			dictFile.open(filename.c_str(), ifstream::in);
			if (!dictFile.fail()) {
				char* word = new char[50];
				dictFile.getline(word, 50);
				while(!dictFile.eof() && !dictFile.fail()) {
					list.push_back(word);
					dictFile.getline(word, 50);
				}
				dictFile.close();
				return list.size();
			} else return 0;
		}
		string findBestMatch(string str) { // welcome to the rating agency
			// finds best match for str in list and returns it
			
			int rating;
			int bestRating = 0;
			string bestRated;
			bool rightOrder;
			size_t lastPos;
			
			for(size_t i = 0; i < list.size(); i++) { // for all entries in dictionary (an entry may contain multiple words)
				rating = 0;
				rightOrder = true;
				lastPos = -1;
				vector<string> dictWords = stringToWords(list[i]);
				int dictWordsOrigSize = dictWords.size();
				vector<string> strWords = stringToWords(str);
				int strWordsOrigSize = strWords.size();
				// compare each word from dict entry to each word from str
				for(size_t j = 0; j < dictWords.size(); j++) { // for all words in current dictionary entry
					for(size_t k = 0; k < strWords.size(); k++) { // for all words in currently recognized string
						if(strWords[k].compare(dictWords[j]) == 0) { // dictWords contains a word from str
							if(lastPos > j) rightOrder = false; // wrong word order detected, rating-- would be more aggressive
							lastPos = j;
							rating++;
							strWords.erase(strWords.begin() + k );
							k--;
							dictWords.erase(dictWords.begin() + j);
							j--;
							break;
						}
					}
				}
				if(rating <= dictWordsOrigSize/2) rating = 0;
				if(rating > 0) {
					if(rating == dictWordsOrigSize) rating++; // bonus if all words are equal, but order may be different
					if(rightOrder && strWordsOrigSize > 1) rating++; // bonus for correct word order of non-trivial str
				}
				
				if(rating > bestRating) { // update rating
					bestRating = rating;
					bestRated = list[i];
				}
			}
			if(bestRating == 0) bestRated = "";
			
			return bestRated;
		}
				
	private:
		vector<string> list;
		
		vector<string> stringToWords(string str) {
			vector<string> words;
			size_t begin = 0;
			size_t end = str.find_first_of(' ', begin);
			while(end != string::npos) {
				words.push_back(str.substr(begin, end-begin));
				begin = end + 1; // skip space
				end = str.find_first_of(' ', begin);
			}
			words.push_back(str.substr(begin, str.length() - begin));
			return words;
		}
};
